import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Test {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char a=s.charAt(i);
            if(a=='('||a=='{'||a=='[') {
                stack.push(a);
            }else {
                if(stack.empty()) {
                    return false;
                }
                char b=stack.pop();
               if(b=='('&&a!=')'||b=='['&&a!=']'||b=='{'&&a!='}') {
                   return false;
               }
            }
        }
        return true;
    }
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    //出入栈匹配
        int pA=0;
        int pB=0;
        int size=popA.length;
        Stack <Integer> stack=new Stack<>();
        while (pB<size) {
            if(!stack.empty()&&stack.peek()==popA[pB]) {
                pB++;
                stack.pop();
            } else {
                if(pA==size){
                    return false;
                }
                stack.push(pushA[pA]);
                pA++;
            }
        }
        return true;
    }
}
class MinStack {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MinStack() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void push(int val) {
        if(stack2.empty()) {
            stack2.push(val);
        }else {
            if(stack2.peek()>val) {
                stack2.push(val);
            }
        }
        stack1.push(val);
    }

    public void pop() {
        if(stack1.peek().equals(stack2.peek())) {
            stack2.pop();
        }
        stack1.pop();
    }

    public int top() {
        return stack1.peek();
    }

    public int getMin() {
        return stack2.peek();
    }
}
class MyStack {
    //队列实现栈
    Queue<Integer> queue1;

    public MyStack() {
        queue1=new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        int n=queue1.size();
        while (n!=1) {
            n--;
            queue1.add(queue1.poll());
        }
        return queue1.poll();
    }

    public int top() {
        int n=queue1.size();
        int p=0;
        while (n!=0) {
            n--;
             p=queue1.poll();
            queue1.add(p);
        }
        return p ;
    }

    public boolean empty() {
    return queue1.isEmpty();
    }
}
class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if(stack2.empty()) {
            while (stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if(stack2.empty()) {
            while (stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.empty()&&stack2.empty();
    }
}
class MyCircularQueue {
    int []array;
    boolean p;
    int front;
    int rear;
    public MyCircularQueue(int k) {
        array=new int[k];
        p=false;
    }

    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        array[rear]=value;
        rear=(rear+1)%array.length;
        if(rear==front) {
            p=true;//满了
        }
        return true;
    }

    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        front=(front+1)%array.length;
        if(front==rear) {
            //p是空就变成false
            p=false;
        }
        return true;
    }

    public int Front() {
        return array[front];
    }

    public int Rear() {
        return array[rear-1];
    }

    public boolean isEmpty() {
    return !p;
    }

    public boolean isFull() {
    return p;
    }
}